1. Field Of Invention
The present invention relates generally to methods and apparatus for transmitting digital data in packet-switched networks. More specifically, the present invention relates to methods and apparatus for supporting tiers of traffic priority levels in a packet-switched network.
2. Background
Today""s integrated service networks are able to support a plurality of different service classes, which may include a bandwidth-guaranteed service class and a best-effort service class. Further, protocols that enable high-speed data access over these integrated service networks, such as cable networks or linked networks (e.g. LANs, WANs, Internet, etc.) have recently been configured to support differentiated Quality of Service (QoS) within selected service classes.
When a scheduler or router has outstanding requests from plurality of different subscribers, it should be able to differentiate and offer better service to selected subscribers (who have subscribed for a higher grade of service) as compared to other subscribers (who have subscribed for lower grade of service). As a result, service providers are now offering differentiated service, particularly within the best-effort service class (herein referred to as xe2x80x9ctiered best-effortxe2x80x9d), whereby different grades or priority levels of service within the best effort class are offered to the subscriber, each with a different pricing plan.
For example, a conventional tiered best-effort service may provide eight differentiated priority levels of best-effort service, each with a different pricing plan. Thus, a subscriber may choose to pay more money for a relatively higher priority best-effort service, whereby, presumably, packets having a relatively higher priority of best-effort service will be routed faster than packets with relatively lower priority best-effort service.
Companies which implement tiered best-effort service typically implement some type of grant prioritization scheme for handling the tiered best-effort traffic. Conventional traffic prioritization algorithms use separate FIFO queues for queuing bandwidth requests (in cable modem networks) or packets (in packet-switched networks) related to a particular priority level of service. A strict priority server is typically used to service the FIFO queues in order of their priority. Thus, for example, in a tiered best-effort service class having eight distinct levels of priority (0-7), 8 separate FIFO queues will typically be provided for servicing bandwidth requests or packets related to each distinct priority level. This can be seen, for example, in FIG. 8 of the drawings.
FIG. 8A shows an example of a plurality of bandwidth request/packets or packets being received at a cable network head end or router. The requests/packets of FIG. 8A are all within the tiered best-effort service class, which in this example includes eight levels of priority (level 7-level 0). Each request/packet has an associated priority level (P) and arrival time (T). FIG. 8B shows a plurality of FIFO queues 810 which are used for queuing the received request/packets of FIG. 8A until each request/packet is able to be processed. As shown in FIG. 8B, each priority level within the tiered best-effort service class has its own respective FIFO queue. Queue 802 corresponds to priority level 7, queue 804 corresponds to priority level 6, and queue 806 corresponds to priority level 0 within the tiered best-effort service class.
A number of conventional scheduling techniques may be employed to service the queued request/packets within queue array 810. One common technique used to service bandwidth requests and/or packets is the use of a strict priority server. The following example provides a brief illustration of how tiered best-effort service is conventionally implemented in a cable modem networks using a strict priority service algorithm.
The process starts with a bandwidth request being sent on the upstream channel by a cable modem at the subscriber end. When the bandwidth request is. received at the cable head end, the service ID (SID) of the cable modem is identified, and from this service ID the particular class of service (i.e. static priority level) associated with the requesting modem""s service class is determined. The received bandwidth request is then enqueued in the appropriate FIFO queue within the queue array 810 corresponding to it""s associated level of priority. Thus, for example, bandwidth request A (FIG. 8A) is associated with priority 7, and therefore enqueued in queue 802 of FIG. 8B. The remainder of the bandwidth requests B-K of FIG. 8A are similarly queued within queue array 810, according to each request""s associated priority level.
A static priority server is used to service the queued bandwidth requests of FIG. 8B. According to the static priority service algorithm, FIFO queues associated with the highest priority level(s) are serviced completely before serving FIFO queues associated with lower priority levels. In the example of FIG. 8, the queued bandwidth requests in FIFO queue 802 would be serviced first (until the queue is empty), followed by queue 804, and eventually queue 806.
One common problem associated with conventional prioritization techniques such as the above-described strict priority scheduling technique, is the requirement of maintaining a separate FIFO queue for each respective priority level within a particular service class for each individual upstream channel [i]. This requirement not only increases complexity and overhead of the network, but also decreases resource utilization since a predetermined amount of memory is typically reserved and allocated for implementing each queue within structure 810, meaning that this allocated memory is unavailable for use for other purposes. Another drawback to the above-described technique is that it is not easily scalable to accommodate changes in the number of static priority levels within a particular service class. In other words, an additional and separate queue must be implemented for each new priority level included within a particular service class. Furthermore, the software for the scheduling algorithm must also be modified to accommodate servicing of the additional priority queues.
Another problem of the above-described technique relates to starvation of low priority traffic. For example, in serving the bandwidth requests of FIG. 8B in the manner described above, it is possible to get a continuous supply of bandwidth requests in the higher priority FIFO queues, which results in starvation of the bandwidth requests queued in the lower priority FIFO queues. To address this problem, it is often necessary to implement a weighted round robin servicing algorithm which uses a fairness algorithm in serving the FIFO queues to ensure that the low priority FIFO queues are sufficiently service so as not to be starved by a continues supply of bandwidth requests in the higher priority FIFO queues.
The round robin scheduling technique is commonly known to those skilled in the art and is described, for example, in the publication xe2x80x9cRound-Robin Space Scheduling for Max-Min Fairness in Data Networks,xe2x80x9d by Ellen L. Hahne, IEEE Journal on Selected Areas in Communications, Volume 9, pages 1024-1036, September 1991, herein incorporated by reference in its entirety for all purposes.
In the weighted Round Robin server implementation, each FIFO queue is pre-assigned a weight, which for example, may be expressed in terms of a number of rounds (e.g. bandwidth requests) to be dequeued from a particular queue during a given cycle, or expressed in terms of a number of bytes to be processed from that queue during a given cycle. By assigning higher weights to the higher priority FIFO queues, a greater number of packets will be processed from these queues, thereby achieving prioritization. At the same time, assigning a small weight to the lower priority queues ensures that at least a minimum number of rounds will be processed from these queues during a given cycle. In this way, starvation of lower priority traffic is avoided.
However, the use of a weighted Round Robin server to service the FIFO queues introduces complexity into the priority service as compared to the conventional strict priority server technique. Moreover, above-described problems are common to both grant schedulers in cable modem head ends and packet schedulers in packet-switched networks.
It is desirable, therefore, to provide a technique for servicing traffic corresponding to a plurality of differentiated levels within a particular service class which is easily scalable and which can support any number of service levels (i.e, static service class priorities) without incurring overhead of maintaining separate FIFO queues for each priority level. Additionally, it is desirable to provide a technique for serving traffic corresponding to a plurality of differentiated levels within a particular service class which does not rely on a separate priority server or round robin scheduling algorithm with an explicit fairness algorithm to avoid starvation of low priority traffic.
According to specific embodiments of the invention, a technique is provided for servicing traffic in a packet-switched, integrated services network which supports a plurality of different service classes. The technique of the present invention uses a single data structure for implementing differentiated levels of service priority within a particular service class. The technique is easily scalable and can support any number of different priority levels without incurring overhead of maintaining separate FIFO queues for each priority level within a particular service class. Additionally, the technique of the present invention does not require the use of an explicit queue server (e.g. strict priority or weighted round robin) or explicit fairness algorithm to avoid starvation of low priority traffic.
According to a specific embodiment of the present invention, a method is provided for handling traffic in a packet-switched integrated services network which supports a plurality of different service classes. The method comprises the steps of receiving at a first arrival time (T1), a first bandwidth request, the first bandwidth request being associated with a particular priority class of service (PCM1); and receiving at a second arrival time (T2), a second bandwidth request, the second bandwidth being associated with a different priority class of service (PCM2) The method further includes the block of calculating a respective priority index value for each received bandwidth request, wherein the priority index value is a function of the arrival time and priority class of each respective bandwidth request. The first and second bandwidth requests are then enqueued within a common queuing structure in an order based upon their respective priority index values. Bandwidth requests queued within the queuing structure are serviced in an order based upon their respective priority index values. An additional aspect of this embodiment includes the block of calculating each respective priority index value by subtracting a product of the priority class of service value from the arrival time value associated with each respective bandwidth request.
A second specific embodiment of the present invention provides a method for handling traffic in a packet-switched integrated services network which supports a plurality of different service classes. The method includes the steps of receiving a bandwidth request at an arrival time (T), the bandwidth request being associated with one of a plurality of different priority classes of service, the one priority class (PCM) having a numeric value associated therewith; and assigning a respective priority index value to the received bandwidth request, wherein the priority index value is calculated by subtracting a product of the PCM value from the T value. The received bandwidth request is then enqueued within a sorted queuing structure in an order based upon its priority index value. An additional aspect of this embodiment includes the block of calculating the priority index value (Pindex) according to: Pindex=Txe2x88x92(PCM*PRIORITY_WEIGHT), wherein the PRIORITY_WEIGHT value is a predetermined constant.
A third aspect of the present invention is directed to a method for handling traffic in a packet-switched integrated services network which supports a plurality of different service classes. The method comprises the steps of receiving at a first arrival time (T1), a first packet, the first packet being associated with a particular priority class of service (PCM1); and receiving at a second arrival time (T2), a second packet, the second bandwidth being associated with a different priority class of service (PCM2). The method further includes the block of calculating a respective priority index value for each received packet, wherein the priority index value is a function of the arrival time and priority class of each respective packet. The first and second packets are then enqueued within a common queuing structure in an order based upon their respective priority index values. Packets queued within the queuing structure are serviced in an order based upon their respective priority index values. An additional aspect of this embodiment includes the block of calculating each respective priority index value by subtracting a product of the priority class of service value from the arrival time value associated with each respective packet.
A fourth specific embodiment of the present invention is directed to a method for handling traffic in a packet-switched integrated services network which supports a plurality of different service classes. The method includes the steps of receiving a packet at an arrival time (T), the packet being associated with one of a plurality of different priority classes of service, the one priority class (PCM) having a numeric value associated therewith; and assigning a respective priority index value to the received packet, wherein the priority index value is calculated by subtracting a product of the PCM value from the T value. The received packet is then enqueued within a sorted queuing structure in an order based upon its priority index value. An additional aspect of this embodiment includes the block of calculating the priority index value (Pindex) according to: Pindex=Txe2x88x92(PCM*PRIORITY_WEIGHT), wherein the PRIORITY_WEIGHT value is a predetermined constant.
A fifth specific embodiment of the present invention provides a computer program product for handling traffic in a packet-switched integrated services network which supports a plurality of different service classes. The computer program product includes at least one computer useable medium having computer readable code embodied therein. The computer readable code comprises computer code for determining an arrival time (T) and a service class priority (PCM) associated with a received bandwidth request; computer code for assigning a respective priority index value (Pindex) to the received bandwidth request, wherein the priority index value is calculated by subtracting a product of the PCM value from the T value; and computer code for enqueuing the received bandwidth request within a sorted queuing structure in an order based upon its Pindex value. An additional aspect of this embodiment includes computer code for calculating the priority index value (Pindex) according to: Pindex=Txe2x88x92(PCM*PRIORITY_WEIGHT), wherein the PRIORITY_WEIGHT value is a predetermined constant.
A sixth specific embodiment of the present invention provides a computer program product for handling traffic in a packet-switched integrated services network which supports a plurality of different service classes. The computer program product includes at least one computer useable medium having computer readable code embodied therein. The computer readable code comprises computer code for determining an arrival time (T) and a service class priority (PCM) associated with a received packet; computer code for assigning a respective priority index value (Pindex) to the received packet, wherein the priority index value is calculated by subtracting a product of the PCM value from the T value; and computer code for enqueuing the received packet within a sorted queuing structure in an order based upon its Pindex value. An additional aspect of this embodiment includes computer code for calculating the priority index value (Pindex) according to: Pindex=Txe2x88x92(PCM*PRIORITY_WEIGHT), wherein the PRIORITY_WEIGHT value is a predetermined constant.
A seventh specific embodiment of the present invention provides a router for handling traffic in a packet-switched, integrated services network which supports a plurality of different service classes. The router includes means for determining an arrival time (T) and a service class priority value (Pp) associated with a received packet; means for assigning a respective priority index value (Pindex) to the received packet, wherein the priority index value is calculated by subtracting a product of the PCM value from the T value; and means for enqueuing the received packet within a sorted queue in an order based upon the Pindex value. An additional aspect of this embodiment includes means for calculating the priority index value according to: Pindex=Txe2x88x92(Pp*PRIORITY_WEIGHT), wherein the PRIORITY_WEIGHT value is a predetermined constant.
An eighth specific embodiment of the present invention provides a cable router for handling traffic in a packet-switched, integrated services network which supports a plurality of different service classes. The router includes means for determining an arrival time (T) and a service class priority value (PCM) associated with a received bandwidth request; means for assigning a respective priority index value (Pindex) to the received bandwidth request, wherein the priority index value is calculated by subtracting a product of the PCM value from the T value; and means for enqueuing the received bandwidth request within a sorted queue in an order based upon the Pindex value. An additional aspect of this embodiment includes means for calculating the priority index value according to: Pindex=Txe2x88x92(PCM*PRIORITY_WEIGHT), wherein the PRIORITY_WEIGHT value is a predetermined constant.
A ninth specific embodiment of the present invention provides a cable modem termination system (CTMS) in a cable modem network for handling traffic in a packet-switched integrated services network which supports a plurality of different service classes. The system comprises, among other things, means for determining an arrival time (T) and a service class priority (PCM) associated with a received bandwidth request; means for assigning a respective priority index value (Pindex) to the received bandwidth request, wherein the priority index value is calculated by subtracting a product of the PCM value from the T value; and means for enqueuing the received bandwidth request within a sorted queuing structure in an order based upon its Pindex value. An additional aspect of this embodiment includes means for calculating the priority index value (Pindex) according to: Pindex=Txe2x88x92(PCM*RIORITY_WEIGHT), wherein the PRIORITY_WEIGHT value is a predetermined constant.
Additional features and advantages of the present invention will become apparent from the following description of its preferred embodiments, which descriptions should be take in conjunction with the accompanying drawings.